Interlaced video has been widely adopted by current TV transmission standards, including PAL, NTSC and SECAM, because it can reduce large area flicker without an increase in transmission bandwidth. It is also used in digital TV systems in which the digital video signal may be encoded by MPEG-1/2/4, H.261/3/4, or a Chinese standard called AVS. However, it introduces several visual artifacts such as edge flicker, interline flicker, and line crawling. In contrast, progressive video has been adopted by the PC community and internet broadcasting, because it does not have the visual artifact in interlaced video and simplifies many image-processing tasks. In order to provide compatibility with existing TV transmission standards, de-interlacing is needed to convert interlaced video to progressive video. In addition, the current digital TV system supports both interlaced and progressive video, both standards will therefore continue to co-exist in the future and de-interlacing algorithms are needed for interoperability between interlaced and progressive video systems.
NTSC video has 30 frames per second (fps) with a resolution of 720×480 pixels for each frame. PAL and SECAM video have 25 fps with a resolution of 720×576 pixels. In these interlaced video systems, there are 2 fields in each frame as shown in FIG. 1. One field is called the upper field or even field and consists of all the even lines (line 0, 2, 4, and so on) of the frame captured at a time t1. The second field is called the lower field or odd field, and it contains all the odd lines (lines 1, 3, 5, and so on) of the frame captured at time t2. The time t1 is earlier than t2 by 1/60th second in the case of 30 fps or 1/50th second in the case of 25 fps. If one frame has N lines, then a field is a vertically-subsampled version of the frame (thus called field instead of frame) containing N/2 lines. The upper field and lower field are interleaved together to form a frame for transmission and storage. If there is motion between the two fields, some “comb” artifacts are present.
The problem of deinterlacing is how to generate a frame given only a single field (even or odd). In other words, given a vertically-subsampled frame (an even or odd field), deinterlacing is the problem of how to interpolate or generate the missing lines. The present invention relates to a novel deinterlacing algorithm.
One of the simplest deinterlacing algorithms is zero-order-hold (also called line doubling) as shown in FIG. 2, in which a line is simply repeated to fill up the missing line. In other words, each missing pixel X is copied from the corresponding top pixel B. The zero-order-hold algorithm suffers from severe staircase artifacts. Another simple deinterlacing algorithm is vertical-averaging as shown in FIG. 3, in which the missing line is generated as the average of the two neighboring lines. In other words, each missing pixel X is the average of the corresponding top pixel B and the bottom pixel E. The line-averaging tends to blur the image significantly, especially around edges.
Most other existing deinterlacing algorithms estimate the edge orientation by defining a correlation measurement and interpolates the missing pixel along the estimated edge direction. One well-known spatial de-interlacing algorithm is edge-based line averaging (ELA). The ELA algorithm utilizes the directional correlation between pixels to estimate the edge orientation and interpolate the missing field along the edge direction. The directional correlation is defined in terms of pixel intensity change along a certain direction. ELA performs well in regions with a dominant edge because the edge direction can be estimated accurately. However, in high frequency regions or horizontal edge regions, poor visual quality may result due to inaccurate estimation of edge orientation. In addition, the number of directions for interpolation is fixed, which implies the algorithm cannot adapt to local image characteristics. For images with a near horizontal edge, the most correlated direction may not be included in the testing and this can result in a poor deinterlaced frame. To produce high quality deinterlaced frames for images with different edge orientation, the simplest way is to increase the number of directions to be tested. However, increasing the number of directions generally increases the chance of getting errors because the correlation measurement cannot perfectly represent the directional correlation for the missing pixel.
Due to the weakness of the existing ELA algorithm, several algorithms have been proposed for converting interlaced video into progressive format. The E-ELA tries to improve the accuracy of ELA by introducing additional measurement. First, it classifies the edge direction into three sides: bias left, vertical and bias right by the pixel intensity change along the −45 deg, vertical and +45 deg directions. Then it applies the traditional ELA algorithm on only one side. The A-ELA tries to interpolate the missing pixels in horizontal edge regions by a majority principle. The 3×3 neighbors are divided into two clusters and the one that has more elements is averaged to produce the missing pixels.